public class Main {
    //任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，
    // 左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，
    // 然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止

    public static void quickSort(int[] arr) {
        quick(arr,0,arr.length-1);
    }

    private static void quick(int[] arr,int start,int end) {
        if(start >= end) return;

        //优化1：三数取中
//        int index = middleNum(arr,start,end);//找到中间下标
//        swap(arr,index,start);//和第一个数字交换

        int pivot = partition2(arr,start,end);
        quick(arr,start,pivot-1);
        quick(arr,pivot+1,end);
    }
    //Hoare法
    private static int partition(int[] arr,int left,int right) {
        //把left作为基准元素
        int tmp = arr[left];
        //把left下标记录下来
        int t = left;
        while (left < right) {
            while (left < right && arr[right] >= tmp) {
                right--;
            }
            while (left < right && arr[left] <= tmp) {
                left++;
            }
            swap(arr,left,right);
        }
        //把基准元素交换到中间
        swap(arr,left,t);
        //返回基准元素的下标
        return left;
    }
    //前后指针
    private static int partition2(int[] arr,int left,int right) {
        int d = left + 1;
        int pivot = arr[left];
        for (int i = left+1; i <= right; i++) {
            if(arr[i] < pivot) {
                swap(arr,i,d);
                d++;
            }
        }
        swap(arr,d-1,left);

        return d-1;
    }

    private static void swap(int[] arr,int a,int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
    public static void main(String[] args) {
        int[] arr = new int[] {1,4,5,2,6,7};
        quickSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            System.out.print(" ");
        }

    }
}
